package depthorder;
import entity.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class InOrderTraversal {
    /*
    * 二叉树的后序遍历
    * 给你二叉树的根节点 root ，返回它节点值的 后序 遍历。
    *
    * 树中节点数目在范围 [0, 100] 内
    * -100 <= Node.val <= 100
    * */
    public static void main(String[] args){

    }

    // 我的想法：递归
    public List<Integer> mySolution(TreeNode root){
        List<Integer> list = new ArrayList<>();
        inOrderTraversal(root, list);
        return list;
    }

    public void inOrderTraversal(TreeNode cur, List<Integer> list){
        if(cur == null)
            return;
        inOrderTraversal(cur.left, list); // 左
        list.add(cur.val);  // 中
        inOrderTraversal(cur.right, list); // 右
    }

    // 迭代
    public List<Integer> solution(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 当前有节点没有遍历完
        while (root != null || !stack.isEmpty()){
            // 先深入到最左叶子节点
            while (root != null){
                stack.add(root);
                root = root.left;
            }
            // 此时root为空 弹栈
            root = stack.pollLast();
            // 此时一定为最左节点或者中间节点，访问该节点
            list.add(root.val);
            // 向右
            root = root.right;
        }
        return list;
    }
}

